/*
题目描述：礼物的最大值
给一个二维矩阵，每个位置有一定的价值，只能向下或者向右走，从左上走到右下所经过路径上的价值之和最大
方法：
典型的动态规划
递归式为   f(i,j) = max(f(i,j-1), f(i-1,j)) + gift(i,j);
 */
public class E47 {
    public static void main(String[] args) {
        int[][] gift = {
                {1,10,3,8},
                {12,2,9,6},
                {5,7,4,11},
                {3,7,16,5}
        };
        int res1 = MaxGift1(gift, gift.length - 1, gift[0].length - 1);
        int res2 = MaxGift2(gift, gift.length - 1, gift[0].length - 1);
        System.out.println(res1);
        System.out.println(res2);
    }

    public static int MaxGift1(int[][] gift, int rows, int cols){
        if(rows < 0 || cols < 0){
            return 0;
        }
        return gift[rows][cols] + Math.max(MaxGift1(gift, rows - 1, cols), MaxGift1(gift, rows, cols - 1));
    }

    public static int MaxGift2(int[][] gift, int rows, int cols){
        if(rows < 0 || cols < 0){
            return 0;
        }
        int maxValue = 0;
        while(rows >= 0 && cols >= 0){
            maxValue += gift[rows][cols];
            if(rows - 1 >= 0 && cols - 1 >= 0){
                if(gift[rows - 1][cols] > gift[rows][cols - 1]){
                    rows--;
                }
                else{
                    cols--;
                }
            }
            else if(rows - 1 >= 0){
                rows --;
            }
            else{
                cols--;
            }
        }
        return maxValue;
    }
}
